In the transmission and storage process of data, the received data may be inconsistent with the sent data due to external interference and other reasons. In order to ensure the correctness of data transmission, generally, some encoding and checking methods are applied in the data transmission process. The realizing methods of checking comprise: parity check, cyclic redundancy check (CRC) and so on, wherein the CRC is widely applied in the communication field and other fields due to its high efficiency and performance.
A CRC code is a shortened cyclic code derived from a cyclic code. When applying the CRC, a sender and a receiver perform operation using a same generator polynomial g(x); in addition, the generator polynomial is set by a user and the first coefficient and last coefficient of the g(x) must be 1. The method for processing the CRC mainly comprises: a sender makes the binary data to be sent t(x) be divided by the generator polynomial g(x), and takes the resultant remainder as the CRC code; and when performing the check, it is judged whether a data frame is changed based on whether the calculated check result is 0.
The implementation of the CRC specifically comprises the following steps. Step 1. the data block to be sent is set as a binary polynomial t(x) of m digits and the generator polynomial is set as g(x) of r orders. Plural 0s in the number of r (r zeros) are added to the data block to be sent at its end to make the length of the data block increase to m+r digits, and its corresponding binary polynomial is xrt(x). Step 2. the data to be sent xrt(x) is divided by the generator polynomial g(x), and the resultant remainder is a binary polynomial y(x) of r−1 orders. This binary polynomial y(x) is the CRC code of the t(x) encoded by using the generator polynomial g(x). Step 3. Subtracting y(x) from xrt(x) by module 2 to obtain a binary polynomial xrt′(x), wherein xrt′(x) is the character string to be sent comprising the CRC code.
It can be seen according to above mentioned encoding rule of the CRC that the encoding of the CRC is actually to transform the binary polynomial t(x) of m digits to be sent into the binary polynomial xrt′(x) of m+r digits which can be divided by g(x) without remainder, therefore during decoding, the received data is divided by g(x), and if the remainder herein is zero, it is indicated that the data does not have errors in the transmission process; and if the remainder is not zero, it is indicated that there must be an error in the transmission process.
CRC algorithm can be classified into two types: serial processing and parallel processing, which are explained hereinafter in detail.
FIG. 1 is a flowchart of a serial processing method for a CRC code according to the related art. As shown in FIG. 1, the method for realizing the CRC code by a serial operation method is described by taking the generator polynomial with the highest degree of 4 (i.e., CRC-4) as an example. Here, four registers are needed to implement division operation, and the method comprises the following steps:
S101: Initializing registers to be 0, then storing generator polynomial coefficients in a register array; at the same time, storing the data to be processed into another temporary register array and adding tail bits to the data to be processed, wherein the method for adding tail bits is implemented by adding four 0s to the information bit stream.
S102: Shifting the register array to the left by 1 bit (shifting the one with a large subscript to the one with a small subscript; supplementing the one with the largest subscript by a temporary array; and shifting the one with the smallest subscript out), and reading in the next bit from the information bit stream of the temporary array and writing it in the 0th register.
S103: Judging whether the bit shifted out of the register array is 1, if so, entering S104, otherwise, entering S105.
S104: After the register array undergoing the XOR operation with respect to the generator polynomial, storing it in the register array and returning to S102.
S105: Judging whether the temporary array is completely processed, i.e., judging whether the information bit stream is completely processed, if not, returning to the temporary data register, otherwise, entering S106.
S106: The value of the register array is the CRC, and the calculation ends.
The serial CRC calculation is generally implemented by the structure of line feedback shift registers (LFSRs). The LFSRs have two structures, respectively called type LFSR1 and type LFSR2. FIG. 2 is a schematic diagram of the structure of type LFSR1 according to the related art; and FIG. 3 is a schematic diagram of the structure of type LFSR2 according to the related art.
It can be known from the above description that in the serial processing method, the processing is made with a bit as the unit, so the efficiency is rather low and the calculation load is high; while the parallel processing method can process 4 bits, 8 bits, 16 bits etc. simultaneously, so as to overcome the above defect of the serial processing method.
The parallel processing method is described hereinafter taking the method for processing the CRC calculation of 8 bits data in parallel using a CRC-32 generator polynomial as an example. FIG. 4 is a flowchart of a method for processing a CRC code in parallel according to the related art. As shown in FIG. 4, a register of 4 bytes (reg) is constructed, with an initial value of 0X00000000; the data to be sent is sequentially shifted to reg 0 (the 0 byte of the register, similar for the following), and at the same time, the data of reg3 is shifted out of reg. The shifted data byte determines what data the reg will undergo XOR with. Since the data to be sent has 8 bits, so that there are 256 selections for the XOR, and the 256 selections form a table corresponding to the data of 8 digits, which is called a lookup table.
At present, the number of digits of the CRC code to be calculated in parallel can only be the nth power of 2; however, in different application scenarios, the number of digits of the data needing to be checked may not be the nth power of 2, but may be odd; under such circumstance, it is needed to add 0 to the front of the data until the number of digits of the data meets the condition of the nth power of 2 to implement the calculation of CRC code in parallel, which has increased the load of registers.